<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head><script type="text/javascript" src="https://cdn.jsdelivr.net/gh/opencobra/cobratoolbox@ffa0229fc0c01c9236bb7e961f65712443277719/latest/_static/js/iframeResizer.contentWindow.min.js"></script><meta http-equiv="Content-Type" content="text/html; charset=utf-8"><meta http-equiv="X-UA-Compatible" content="IE=edge,IE=9,chrome=1"><meta name="generator" content="MATLAB 2021a"><title>Determining MinSpan vectors of COBRA model</title><style type="text/css">.rtcContent { padding: 30px; } .S0 { margin: 3px 10px 5px 4px; padding: 0px; line-height: 28.8px; min-height: 0px; white-space: normal; color: rgb(213, 80, 0); font-family: Helvetica, Arial, sans-serif; font-style: normal; font-size: 24px; font-weight: normal; text-align: left;  }
.S1 { margin: 20px 10px 5px 4px; padding: 0px; line-height: 20px; min-height: 0px; white-space: normal; color: rgb(60, 60, 60); font-family: Helvetica, Arial, sans-serif; font-style: normal; font-size: 20px; font-weight: bold; text-align: left;  }
.S2 { margin: 2px 10px 9px 4px; padding: 0px; line-height: 21px; min-height: 0px; white-space: normal; color: rgb(0, 0, 0); font-family: Helvetica, Arial, sans-serif; font-style: normal; font-size: 14px; font-weight: normal; text-align: left;  }
.S3 { margin: 2px 10px 9px 4px; padding: 0px; line-height: 21px; min-height: 0px; white-space: normal; color: rgb(0, 0, 0); font-family: Helvetica, Arial, sans-serif; font-style: normal; font-size: 14px; font-weight: normal; text-align: center;  }
.S4 { margin: 3px 10px 5px 4px; padding: 0px; line-height: 20px; min-height: 0px; white-space: normal; color: rgb(60, 60, 60); font-family: Helvetica, Arial, sans-serif; font-style: normal; font-size: 20px; font-weight: bold; text-align: left;  }
.CodeBlock { background-color: #F7F7F7; margin: 10px 0 10px 0;}
.S5 { border-left: 1px solid rgb(233, 233, 233); border-right: 1px solid rgb(233, 233, 233); border-top: 1px solid rgb(233, 233, 233); border-bottom: 0px none rgb(0, 0, 0); border-radius: 4px 4px 0px 0px; padding: 6px 45px 0px 13px; line-height: 17.234px; min-height: 18px; white-space: nowrap; color: rgb(0, 0, 0); font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 14px;  }
.S6 { border-left: 1px solid rgb(233, 233, 233); border-right: 1px solid rgb(233, 233, 233); border-top: 0px none rgb(0, 0, 0); border-bottom: 0px none rgb(0, 0, 0); border-radius: 0px; padding: 0px 45px 0px 13px; line-height: 17.234px; min-height: 18px; white-space: nowrap; color: rgb(0, 0, 0); font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 14px;  }
.S7 { border-left: 1px solid rgb(233, 233, 233); border-right: 1px solid rgb(233, 233, 233); border-top: 0px none rgb(0, 0, 0); border-bottom: 1px solid rgb(233, 233, 233); border-radius: 0px 0px 4px 4px; padding: 0px 45px 4px 13px; line-height: 17.234px; min-height: 18px; white-space: nowrap; color: rgb(0, 0, 0); font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 14px;  }
.S8 { margin: 10px 10px 9px 4px; padding: 0px; line-height: 21px; min-height: 0px; white-space: normal; color: rgb(0, 0, 0); font-family: Helvetica, Arial, sans-serif; font-style: normal; font-size: 14px; font-weight: normal; text-align: left;  }
.S9 { border-left: 1px solid rgb(233, 233, 233); border-right: 1px solid rgb(233, 233, 233); border-top: 1px solid rgb(233, 233, 233); border-bottom: 1px solid rgb(233, 233, 233); border-radius: 4px; padding: 6px 45px 4px 13px; line-height: 17.234px; min-height: 18px; white-space: nowrap; color: rgb(0, 0, 0); font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 14px;  }</style></head><body><div class = rtcContent><h1  class = 'S0'><span>Determining MinSpan vectors of COBRA model</span></h1><h2  class = 'S1'><span>Author: Aarash Bordbar</span></h2><h2  class = 'S1'><span>Affiliation: Sinopia Biosciences, San Diego, CA USA</span></h2><h2  class = 'S1'><span>Reviewer: James T. Yurkovich</span></h2><h2  class = 'S1'><span>INTRODUCTION</span></h2><div  class = 'S2'><span>In this tutorial, we show how to calculate MinSpan vectors [1] for a COBRA model. COBRA models are predominantly studied under steady-state conditions, thus the null space of the </span><span style=' font-weight: bold;'>S</span><span> matrix is of high interest. MinSpan vectors represent the sparsest linear basis of the null space </span><span style=' font-weight: bold;'>S </span><span>while still maintaining the biological and thermodynamic constraints of the COBRA model (Figure 1). The </span><span style=' font-weight: bold;'>S </span><span>matrix has dimensions (</span><span style=' font-weight: bold;'>m </span><span>x </span><span style=' font-weight: bold;'>n</span><span>) where </span><span style=' font-weight: bold;'>m </span><span>is the number of metabolites and </span><span style=' font-weight: bold;'>n </span><span>is the number of reactions. The linear basis of the null space (</span><span style=' font-weight: bold;'>N</span><span>) has dimensions (</span><span style=' font-weight: bold;'>n </span><span>x </span><span style=' font-weight: bold;'>n-r</span><span>) where </span><span style=' font-weight: bold;'>r </span><span>is the rank of </span><span style=' font-weight: bold;'>S</span><span>. Thus this algorithm calculates </span><span style=' font-weight: bold;'>n-r</span><span> vectors that are linearly independent of each other and also are minimal. For further info on MinSpan, it's derivation, implementation, and uses, see Bordbar et al. 2014 [1].</span></div><div  class = 'S3'><img class = "imageNode" src = "" width = "361" height = "397" alt = "" style = "vertical-align: baseline"></img></div><div  class = 'S2'><span>Figure 1 | Overview of the MinSpan algorithm. (A) A metabolic network is mathematically represented as a stoichiometric matrix (</span><span style=' font-weight: bold;'>S</span><span>). Reaction fluxes (</span><span style=' font-weight: bold;'>v</span><span>) are determined assuming steady state. All potential flux states lie in the null space (</span><span style=' font-weight: bold;'>N</span><span>). (B) The MinSpan algorithm determines the shortest, independent pathways of the metabolic network by decomposing the null space of the stoichiometric matrix to form the sparsest basis. (C) A simplified model for glycolysis and the TCA cycle is presented with 14 metabolites, 18 reactions, and a 4-dimensional null space. Reversible reactions are shown. (D) The four pathways calculed by MinSpan for the simplified model are presented, two of which recapitulate glycolysis and the TCA cycle, while the other two represent other possible metabolic pathways. The flux directions of a pathway through reversible reactions are shown as irreversible reactions. </span></div><h2  class = 'S1'><span>MATERIALS</span></h2><h2  class = 'S1'><span>Equipment Setup</span></h2><div  class = 'S2'><span>Running the MinSpan algorithm requires the installation of a mixed-integer linear programming (MILP) solver. We have used Gurobi v5+ (http://www.gurobi.com/downloads/download-center) which is freely available for academic use. This tutorial and the algorithm has been rigorously tested and support Gurobi v5+. </span><span style=' font-family: monospace;'>detMinSpan</span><span> will not work with GLPK; other solvers are untested.</span></div><h2  class = 'S1'><span>Implementation</span></h2><div  class = 'S2'><span>For MinSpan vectors to be calculated, the model must (1) consist of only reactions that are able to carry flux under that particular condition, (2) allow for the trivial solution (</span><span style=' font-weight: bold;'>v </span><span>= 0) to be feasible, and (3) have the biomass function removed. </span><span style=' font-family: monospace;'>detMinSpan</span><span> will automatically check and complete the first two modifications, but the biomass must be removed manually.</span></div><div  class = 'S2'><span>The algorithm is an iterative pruning of null space basis vectors to the sparsest possible matrix. The problem is NP-hard, meaning that an optimal solution is not guaranteed for large COBRA models; an approximate solution is found by setting a time limit on the MILP calculation.</span></div><h2  class = 'S4'><span>Procedure</span></h2><div  class = 'S2'><span>In this example, we will calculate the MinSpan vectors for the </span><span style=' font-style: italic;'>E. coli</span><span> core network. </span></div><div  class = 'S2'><span>Ensure that the Gurobi MILP and LP solvers are working:</span></div><div class="CodeBlock"><div class="inlineWrapper"><div  class = 'S5'><span style="white-space: normal"><span >test1 = changeCobraSolver(</span><span style="color: rgb(170, 4, 249);">'gurobi'</span><span >, </span><span style="color: rgb(170, 4, 249);">'MILP'</span><span >);</span></span></div></div><div class="inlineWrapper"><div  class = 'S6'><span style="white-space: normal"><span >test2 = changeCobraSolver(</span><span style="color: rgb(170, 4, 249);">'gurobi'</span><span >, </span><span style="color: rgb(170, 4, 249);">'LP'</span><span >);</span></span></div></div><div class="inlineWrapper"><div  class = 'S6'><span style="white-space: normal"><span >test3 = changeCobraSolver(</span><span style="color: rgb(170, 4, 249);">'gurobi'</span><span >, </span><span style="color: rgb(170, 4, 249);">'QP'</span><span >);</span></span></div></div><div class="inlineWrapper"><div  class = 'S6'><span style="white-space: normal"><span style="color: rgb(14, 0, 255);">if </span><span >test1 == 0 || test2 == 0 || test3 == 0</span></span></div></div><div class="inlineWrapper"><div  class = 'S6'><span style="white-space: normal"><span >    error(</span><span style="color: rgb(170, 4, 249);">'minSpan only works with gurobi version 5+'</span><span >);</span></span></div></div><div class="inlineWrapper"><div  class = 'S7'><span style="white-space: normal"><span style="color: rgb(14, 0, 255);">end</span></span></div></div></div><div  class = 'S8'><span>Load the core model:</span></div><div  class = 'S2'><span></span></div><div class="CodeBlock"><div class="inlineWrapper"><div  class = 'S5'><span style="white-space: normal"><span style="color: rgb(14, 0, 255);">global </span><span >CBTDIR</span></span></div></div><div class="inlineWrapper"><div  class = 'S6'><span style="white-space: normal"><span >modelFileName = </span><span style="color: rgb(170, 4, 249);">'ecoli_core_model.mat'</span><span >;</span></span></div></div><div class="inlineWrapper"><div  class = 'S6'><span style="white-space: normal"><span >modelDirectory = getDistributedModelFolder(modelFileName); </span><span style="color: rgb(2, 128, 9);">%Look up the folder for the distributed Models.</span></span></div></div><div class="inlineWrapper"><div  class = 'S6'><span style="white-space: normal"><span >modelFileName= [modelDirectory filesep modelFileName]; </span><span style="color: rgb(2, 128, 9);">% Get the full path. Necessary to be sure, that the right model is loaded</span></span></div></div><div class="inlineWrapper"><div  class = 'S7'><span style="white-space: normal"><span >model = readCbModel(modelFileName);</span></span></div></div></div><div  class = 'S2'><span>The biomass function is then removed from the model using the COBRA function </span><span style=' font-family: monospace;'>removeRxns</span><span>.</span></div><div class="CodeBlock"><div class="inlineWrapper"><div  class = 'S5'><span style="white-space: normal"><span >bmName = {</span><span style="color: rgb(170, 4, 249);">'Biomass_Ecoli_core_w_GAM'</span><span >};</span></span></div></div><div class="inlineWrapper"><div  class = 'S7'><span style="white-space: normal"><span >model = removeRxns(model, bmName);</span></span></div></div></div><div  class = 'S8'><span>The MinSpan algorithm takes the model as input and returns a matrix containing the calculated MinSpan vectors (Table 1). </span></div><div  class = 'S3'><img class = "imageNode" src = "" width = "615" height = "194" alt = "" style = "vertical-align: baseline"></img></div><div  class = 'S2'><span>Table 1 | Inputs and outputs of the </span><span style=' font-family: monospace;'>detMinSpan</span><span> function.</span></div><div  class = 'S2'><span>Running the algorithm on the modified </span><span style=' font-style: italic;'>E. coli</span><span> core model returns the calculated MinSpans for the network:</span></div><div class="CodeBlock"><div class="inlineWrapper"><div  class = 'S5'><span style="white-space: normal"><span >tic</span></span></div></div><div class="inlineWrapper"><div  class = 'S6'><span style="white-space: normal"><span >minSpanVectors = detMinSpan(model);</span></span></div></div><div class="inlineWrapper"><div  class = 'S7'><span style="white-space: normal"><span >toc</span></span></div></div></div><div  class = 'S8'><span style=' font-family: monospace;'>minSpanVectors</span><span> is a matrix that consists of 23 linearly independent vectors. A further description of these vectors is provided and their comparison to Extreme Pathways [2] is provided in the Supplementary Material of Bordbar et al 2014 [1] (Section 1 and Figure S2).</span></div><div  class = 'S2'><span>Numerical properties of the stoichiometric matrix:</span></div><div class="CodeBlock"><div class="inlineWrapper"><div  class = 'S9'><span style="white-space: normal"><span >[nMet,nRxn]=size(model.S)</span></span></div></div></div><div  class = 'S8'><span>Independent dimensions of the right nullspace of the stoichiometric matrix</span></div><div class="CodeBlock"><div class="inlineWrapper"><div  class = 'S9'><span style="white-space: normal"><span >fprintf(</span><span style="color: rgb(170, 4, 249);">'%s%g\n'</span><span >,</span><span style="color: rgb(170, 4, 249);">'Number of right nullspace basis vectors expected: '</span><span >,nRxn-rank(full(model.S)))</span></span></div></div></div><div  class = 'S8'><span>Numerical properties of the minSpan basis:</span></div><div class="CodeBlock"><div class="inlineWrapper"><div  class = 'S5'></div></div><div class="inlineWrapper"><div  class = 'S7'><span style="white-space: normal"><span >[nRxn2,nMinSpanVectors]=size(minSpanVectors)</span></span></div></div></div><div  class = 'S8'><span>Rank of the minSpanVectors</span></div><div class="CodeBlock"><div class="inlineWrapper"><div  class = 'S9'><span style="white-space: normal"><span >fprintf(</span><span style="color: rgb(170, 4, 249);">'%s%g\n'</span><span >,</span><span style="color: rgb(170, 4, 249);">'Rank of minSpanVectors matrix:'</span><span >,rank(full(minSpanVectors)))</span></span></div></div></div><div  class = 'S8'><span></span></div><div class="CodeBlock"><div class="inlineWrapper"><div  class = 'S9'></div></div></div><div  class = 'S8'><span>Check the minSpan is really a basis for the nullspace:</span></div><div class="CodeBlock"><div class="inlineWrapper"><div  class = 'S5'><span style="white-space: normal"><span >fprintf(</span><span style="color: rgb(170, 4, 249);">'%s%g\n'</span><span >,</span><span style="color: rgb(170, 4, 249);">'Should be zero: '</span><span >,norm(model.S*minSpanVectors))</span></span></div></div><div class="inlineWrapper"><div  class = 'S7'><span style="white-space: normal"><span >fprintf(</span><span style="color: rgb(170, 4, 249);">'%s%g\n'</span><span >,</span><span style="color: rgb(170, 4, 249);">'Should be zero (?): '</span><span >,norm(nRxn-rank(full(model.S))-rank(full(minSpanVectors))))</span></span></div></div></div><div  class = 'S8'><span>Investigate the sparsity pattern of the minSpan basis:</span></div><div class="CodeBlock"><div class="inlineWrapper"><div  class = 'S5'><span style="white-space: normal"><span >fprintf(</span><span style="color: rgb(170, 4, 249);">'%s%g\n'</span><span >,</span><span style="color: rgb(170, 4, 249);">'Sparsity ratio of minSpanVectors: '</span><span >,nnz(minSpanVectors)/(nRxn2*nMinSpanVectors))</span></span></div></div><div class="inlineWrapper"><div  class = 'S7'><span style="white-space: normal"><span >spy(minSpanVectors)</span></span></div></div></div><h2  class = 'S1'><span>References</span></h2><div  class = 'S2'><span>[1] Bordbar A, Nagarajan H, Lewis NE, Latif H, Ebrahim A, Federowicz S, Schellenberger J, Palsson BO. "Minimal metabolic pathway structure is consistent with associated biomolecular interactions" </span><span style=' font-style: italic;'>Mol Syst Biol</span><span> </span><span style=' font-weight: bold;'>10:</span><span>737 (2014).</span></div><div  class = 'S2'><span>[2] Schilling CH, Letscher D, Palsson BO. "Theory for the systemic definition of metabolic pathways and their use in interpreting metabolic function from a pathway-oriented perspective. </span><span style=' font-style: italic;'>J Theor Biol </span><span style=' font-weight: bold;'>203:</span><span>229-248 (2000).</span></div>
<br>
<!-- 
##### SOURCE BEGIN #####
%% Determining MinSpan vectors of COBRA model
%% Author: Aarash Bordbar
%% Affiliation: Sinopia Biosciences, San Diego, CA USA
%% Reviewer: James T. Yurkovich
%% INTRODUCTION
% In this tutorial, we show how to calculate MinSpan vectors [1] for a COBRA 
% model. COBRA models are predominantly studied under steady-state conditions, 
% thus the null space of the *S* matrix is of high interest. MinSpan vectors represent 
% the sparsest linear basis of the null space *S* while still maintaining the 
% biological and thermodynamic constraints of the COBRA model (Figure 1). The 
% *S* matrix has dimensions (*m* x *n*) where *m* is the number of metabolites 
% and *n* is the number of reactions. The linear basis of the null space (*N*) 
% has dimensions (*n* x *n-r*) where *r* is the rank of *S*. Thus this algorithm 
% calculates *n-r* vectors that are linearly independent of each other and also 
% are minimal. For further info on MinSpan, it's derivation, implementation, and 
% uses, see Bordbar et al. 2014 [1].
% 
% 
% 
% Figure 1 | Overview of the MinSpan algorithm. (A) A metabolic network is mathematically 
% represented as a stoichiometric matrix (*S*). Reaction fluxes (*v*) are determined 
% assuming steady state. All potential flux states lie in the null space (*N*). 
% (B) The MinSpan algorithm determines the shortest, independent pathways of the 
% metabolic network by decomposing the null space of the stoichiometric matrix 
% to form the sparsest basis. (C) A simplified model for glycolysis and the TCA 
% cycle is presented with 14 metabolites, 18 reactions, and a 4-dimensional null 
% space. Reversible reactions are shown. (D) The four pathways calculed by MinSpan 
% for the simplified model are presented, two of which recapitulate glycolysis 
% and the TCA cycle, while the other two represent other possible metabolic pathways. 
% The flux directions of a pathway through reversible reactions are shown as irreversible 
% reactions. 
%% MATERIALS
%% Equipment Setup
% Running the MinSpan algorithm requires the installation of a mixed-integer 
% linear programming (MILP) solver. We have used Gurobi v5+ (http://www.gurobi.com/downloads/download-center) 
% which is freely available for academic use. This tutorial and the algorithm 
% has been rigorously tested and support Gurobi v5+. |detMinSpan| will not work 
% with GLPK; other solvers are untested.
%% Implementation
% For MinSpan vectors to be calculated, the model must (1) consist of only reactions 
% that are able to carry flux under that particular condition, (2) allow for the 
% trivial solution (*v* = 0) to be feasible, and (3) have the biomass function 
% removed. |detMinSpan| will automatically check and complete the first two modifications, 
% but the biomass must be removed manually.
% 
% The algorithm is an iterative pruning of null space basis vectors to the sparsest 
% possible matrix. The problem is NP-hard, meaning that an optimal solution is 
% not guaranteed for large COBRA models; an approximate solution is found by setting 
% a time limit on the MILP calculation.
%% Procedure
% In this example, we will calculate the MinSpan vectors for the _E. coli_ core 
% network. 
% 
% Ensure that the Gurobi MILP and LP solvers are working:

test1 = changeCobraSolver('gurobi', 'MILP');
test2 = changeCobraSolver('gurobi', 'LP');
test3 = changeCobraSolver('gurobi', 'QP');
if test1 == 0 || test2 == 0 || test3 == 0
    error('minSpan only works with gurobi version 5+');
end
%% 
% Load the core model:
% 
% 

global CBTDIR
modelFileName = 'ecoli_core_model.mat';
modelDirectory = getDistributedModelFolder(modelFileName); %Look up the folder for the distributed Models.
modelFileName= [modelDirectory filesep modelFileName]; % Get the full path. Necessary to be sure, that the right model is loaded
model = readCbModel(modelFileName);
%% 
% The biomass function is then removed from the model using the COBRA function 
% |removeRxns|.

bmName = {'Biomass_Ecoli_core_w_GAM'};
model = removeRxns(model, bmName);
%% 
% The MinSpan algorithm takes the model as input and returns a matrix containing 
% the calculated MinSpan vectors (Table 1). 
% 
% 
% 
% Table 1 | Inputs and outputs of the |detMinSpan| function.
% 
% Running the algorithm on the modified _E. coli_ core model returns the calculated 
% MinSpans for the network:

tic
minSpanVectors = detMinSpan(model);
toc
%% 
% |minSpanVectors| is a matrix that consists of 23 linearly independent vectors. 
% A further description of these vectors is provided and their comparison to Extreme 
% Pathways [2] is provided in the Supplementary Material of Bordbar et al 2014 
% [1] (Section 1 and Figure S2).
% 
% Numerical properties of the stoichiometric matrix:

[nMet,nRxn]=size(model.S)
%% 
% Independent dimensions of the right nullspace of the stoichiometric matrix

fprintf('%s%g\n','Number of right nullspace basis vectors expected: ',nRxn-rank(full(model.S)))
%% 
% Numerical properties of the minSpan basis:


[nRxn2,nMinSpanVectors]=size(minSpanVectors)
%% 
% Rank of the minSpanVectors

fprintf('%s%g\n','Rank of minSpanVectors matrix:',rank(full(minSpanVectors)))
%% 
% 


%% 
% Check the minSpan is really a basis for the nullspace:

fprintf('%s%g\n','Should be zero: ',norm(model.S*minSpanVectors))
fprintf('%s%g\n','Should be zero (?): ',norm(nRxn-rank(full(model.S))-rank(full(minSpanVectors))))
%% 
% Investigate the sparsity pattern of the minSpan basis:

fprintf('%s%g\n','Sparsity ratio of minSpanVectors: ',nnz(minSpanVectors)/(nRxn2*nMinSpanVectors))
spy(minSpanVectors)
%% References
% [1] Bordbar A, Nagarajan H, Lewis NE, Latif H, Ebrahim A, Federowicz S, Schellenberger 
% J, Palsson BO. "Minimal metabolic pathway structure is consistent with associated 
% biomolecular interactions" _Mol Syst Biol_ *10:*737 (2014).
% 
% [2] Schilling CH, Letscher D, Palsson BO. "Theory for the systemic definition 
% of metabolic pathways and their use in interpreting metabolic function from 
% a pathway-oriented perspective. _J Theor Biol_ *203:*229-248 (2000).
##### SOURCE END #####
-->
</div></body></html>